package Algorithm.Tree;

/**
 * @Author cj
 * @Date 2022/8/30 20:30
 */
public class getNextNode {

    static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int val) {
            this.value = val;
        }

        public Node getNextNode1(Node node) {
            if (node == null) {
                return null;
            }
            // 情况1：node有右子树
            if (node.right != null) {
                // 找到右子树最左节点
                return getLeftMost(node.right);
            }
            // 情况2：node没有右子树
            if (node == node.parent.left) {
                return node.parent;
            } else { // 向上找
                Node parent = node.parent;
                while (parent != null && parent.left != node) {
                    node = parent;
                    parent = node.parent;
                }
                return parent;
            }

        }

        private Node getLeftMost(Node node) {
            if (node == null) {
                return null;
            }
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    }
}
